package 面试;

/**
 * 主要元素
 *
 * 数组中占比超过一半的元素称之为主要元素。给你一个 整数 数组，找出其中的主要元素。若没有，返回 -1 。请设计时间复杂度为 O(N) 、空间复杂度为 O(1) 的解决方案。
 */

public class L1710_important {

    public static void main(String[] args) {
        System.out.println(new L1710_important().majorityElement(new int[]{1, 2, 5, 9, 5, 9, 5, 5, 5}));
    }

    /**
     *  Boyer-Moore 投票算法 (终极无敌最优解)
     *
     */
    public int majorityElement(int[] nums) {
        int candidate = -1;             // 候选值
        int count = 0;                  // 记录个数
        for (int num : nums) {          // 第一次遍历，如果count 为0，则更换候选值，如果相同 则count加1，否则减1
            if (count == 0) {
                candidate = num;
            }
            if (num == candidate) {
                count++;
            } else {
                count--;
            }
        }
        count = 0;
        int length = nums.length;       // 第二次遍历看候选者是否数量超过一半
        for (int num : nums) {
            if (num == candidate) {
                count++;
            }
        }
        return count * 2 > length ? candidate : -1;
    }

/*    作者：LeetCode-Solution
    链接：https://leetcode-cn.com/problems/find-majority-element-lcci/solution/zhu-yao-yuan-su-by-leetcode-solution-xr1p/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。*/
}
